package com.mj.listen1._08_红黑树.tree;

import java.util.Comparator;

/**
 * 二叉搜索树
 *
 * @param <E>
 */
public class BinarySearchTree<E> extends BinaryTree<E> {

    /**
     * 默认使用比较器比较，比较器更灵活，由使用者来定义
     */
    private Comparator<E> comparator;

    public BinarySearchTree() {

    }

    public BinarySearchTree(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    // 添加元素
    public void add(E element) {
        elementNotNullElement(element);

        // 第一次添加
        if (root == null) {
            root = createNode(element, null);
            size++;
            // 新添加节点之后的处理
            afterAdd(root);
            return;
        }

        // 不是第一次添加。需要区分添加的元素与当前节点的值哪个大。
        // 比当前节点的值大了往右找，小了往左找
        // 寻找添加节点的父节点
        Node<E> node = root;
        // 记录父节点
        Node<E> parent = root;
        int com = 0;
        while (null != node) {
            com = compare(element, node.element);
            parent = node;
            if (com < 0) {
                // 往左边找
                node = node.left;
            } else if (com > 0) {
                node = node.right;
            } else {
                node.element = element;
                return;
            }
        }

        // 把元素放入到二叉搜索树上
        // 插入到左边还是右边，依然是根据 compare(element, node.element);结果
        Node<E> newNode = createNode(element, parent);
        if (com < 0) {
            // 插入到左边
            parent.left = newNode;
        } else {
            // 插入到右边
            parent.right = newNode;
        }
        size++;
        afterAdd(newNode);
    }

    /**
     * 添加节点以后做调整
     *
     * @param node
     */
    protected void afterAdd(Node<E> node) {

    }

    // 删除元素
    public void remove(E element) {
        remove(node(element));
    }

    // 传入某个节点，然后删除掉
    private void remove(Node<E> node) {
        if (node == null) return;
        size--;

        // 删除的节点度为2
        // ---找到节点的后继节点，后继节点分2种情况：度为0(叶子节点)，度为1(如果度为2，一定还会往下继续找)
        // 后继节点值覆盖要删除节点的值；删除掉找到的后继节点，删除后继几点转换为删除度为1或者为0的节点了
        if (node.hasTwoChildren()) {
            // 要删除节点度为2
            // 找到节点的后继节点
            Node<E> successor = successor(node);
            // 值覆盖
            node.element = successor.element;
            // successor变为新的要被删除的节点
            node = successor;
        }

        // 删除的节点度为1：
        Node<E> replaceNode = node.left != null ? node.left : node.right;// 替代者
        if (replaceNode != null) {// 删除节点度为1
            // 删除节点的父节点指向删除节点的父节点
            replaceNode.parent = node.parent;
            if (node.parent == null) {
                // 删除的是根节点，改变root指向
                root = replaceNode;
            }
            if (node == node.parent.left) {
                // 删除节点在左边
                node.parent.left = replaceNode;
            } else {
                // 删除节点在右边
                node.parent.right = replaceNode;
            }
            // ---有左子树：child.parent = node.parent;node.parent.left = child
            // ---有右子树：child.parent = node.parent;node.parent.right = child;

            // 删除以后的调整
            afterRemove(node, replaceNode);
        } else if (node == root) {// 删除的节点度为0
            // 删除的节点度为0，且是根节点
            node.parent = null;
            root = null;

            // 删除以后的调整
            afterRemove(node, null);
        } else {// 删除的节点度为0，是叶子节点
            if (node == node.parent.left) {
                // 节点在左侧
                node.parent.left = null;
            } else {
                // 节点在右侧
                node.parent.right = null;
            }
            // 删除以后的调整
            afterRemove(node, null);
        }
    }

    /**
     * 删除节点以后做调整
     *
     * @param node
     * @param replaceNode  替换的节点
     */
    protected void afterRemove(Node<E> node, Node<E> replaceNode) {

    }

    // 根据元素获取某个节点
    private Node<E> node(E element) {
        if (element == null) return null;
        // 从root开始寻找
        Node<E> node = root;
        while (node != null) {
            int com = compare(element, node.element);
            if (com == 0) {
                // 找到后返回
                return node;
            } else if (com < 0) {
                // element 小于 node.element 往节点的左边找
                node = node.left;
            } else {
                // element 大于 node.element 往节点的右边找
                node = node.right;
            }
        }
        // node = null
        return null;
    }

    // 是否包含某元素
    public boolean contains(E element) {
        return node(element) == null;
    }

    // 两个对象比较
    // 如果返回值=0，两个值相等；小于0，e1<e2；大于0，e1>e2
    private int compare(E e1, E e2) {
        if (comparator != null) {
            return comparator.compare(e1, e2);
        }
        // 二叉搜索树必须具备可比较性。没有实现比较器的话，使用自带的Comparable的compareTo接口
        return (((Comparable<E>) e1).compareTo(e2));
    }

    // 添加的元素不能为null
    private void elementNotNullElement(E element) {
        if (null == element) {
            throw new IllegalArgumentException("element must not be null");
        }
    }
}